Internet protocol (IP) routing involves transmitting packets from a source to a destination through a series of hops. Lookups are performed frequently in the process of handling network traffic. For example, lookups may be used to implement an access control list (ACL), policy routing, rate shaping, and quality of service (QoS). Determining the next hop of a packet involves, for example, looking up the destination address of the packet in a route lookup table. When performing a lookup, information from incoming packets, such as header information, is used to compare against information stored in a lookup table to determine how the packet should be handled. In the process of handling network traffic, multiple hookups may be performed using information from different protocol layers, such as layer three (3) and layer four (4), where the layers are defined by the International Standards Organization (ISO) in the Open System Interconnection (OSI) model. As defined in the OSI model, layer 3 (L3) (also referred to as the network layer) is used to route data to different routers based on destination IP addresses. Layer 4 (L4) (also referred to as the transport layer) can be used to ensure delivery of an entire file or message. L3 lookups are commonly performed in order to determine a next hop for a packet. L4 lookups are commonly performed to implement a traffic distribution policy or for access control.
The speed with which route lookups are performed is one factor that determines the throughput of a router. Traditional routers have used random access memory (RAM) and software based lookups to determine the next hop of packets. However, RAM and software based lookups have become a bottleneck in newer high-speed routers.
CAM arrays are now being used as a way to speed route table lookups. “Ternary” or “tertiary” CAMs are being used to perform route table lookups in networks that require longest prefix matching, such as networks that utilize Classless Inter Domain Routing (CIDR). Ternary CAMs can perform compare operations on bits that are “0”, “1”, or “X”, where “X” is a wildcard or “don't care” value. In order to accomplish compare operations on bits that are “0”, “1”, or “X”, ternary CAMs store a prefix mask word in addition to a CAM entry word. The prefix mask word associated with each CAM entry indicates the number of significant bits that must be matched in each CAM entry. That is, the prefix mask word identifies the bits that fall into the “X” category.
CIDR specifies longest prefix matching and because multiple matches may occur in a route lookup, the longest prefix match must be determined from the multiple matches. The most common technique for determining the longest prefix match from multiple matches involves prioritizing all of the route entries in a lookup table by prefix length, with the longest prefix length having the highest priority and the shortest prefix length having the lowest priority. The longest prefix match is determined by selecting the matching entry with the highest priority among all of the matching entries.
When a best match is made, the system typically checks a database to find routing information associated with the best match. For example, if a router receives a packet with a destination IP address of A.B.C.D, a best match in the database may be A.B.C.D, and the database may include an entry A.B.C.D with routing information associated with that entry. The system forwards the packet according to the routing information.
When lookup rules are updated, the system matches packets to the updated rules and forwards the packets accordingly. The rules are typically added one at a time. Thus, a first rule for a traffic class may be active while a second rule is not. This results in packets matching transient state rules (i.e., rules that are going to be changed in accordance with a rule set that is currently being added). It would be advantageous to implement a new rule set while avoiding transient state rule matches.